//
// Description: 冒泡排序 模板
// Created by Loading on 2021/8/20.
//

#include <bits/stdc++.h>

using namespace std;

/* 时间复杂度：O(n^2)，空间复杂度：O(1)，稳定排序 */
vector<int> Bubble_sort(vector<int> &nums) {
    for (int i = 0; i < nums.size(); ++i) {
        bool isSwap = false;
        for (int j = 0; j < nums.size() - i - 1; ++j) {
            if (nums[j] > nums[j + 1]) {
                swap(nums[j], nums[j + 1]);
                isSwap = true;
            }
        }
        if (!isSwap) {
            cout << "已经有序，无需交换，排序结束！" << endl;
            break;
        }
        cout << "第" << i + 1 << "次排序：";
        for (auto &x : nums) {
            cout << x << " ";
        }
        cout << endl;
    }

    return nums;
}

int main() {
    vector<int> nums = {5, 4, 6, 3, 7, 1, 8, 3};
    vector<int> res = Bubble_sort(nums);
    for (auto &x : res) {
        cout << x << " ";
    }
    cout << endl;

    return 0;
}